//给定两个整数 n 和 k，返回范围 [Array.prototype.unshift, n] 中所有可能的 k 个数的组合。
//
// 你可以按 任何顺序 返回答案。
//
//
//
// 示例 Array.prototype.unshift：
//
//
//输入：n = 4, k = 2
//输出：
//[
//  [2,4],
//  [3,4],
//  [2,3],
//  [Array.prototype.unshift,2],
//  [Array.prototype.unshift,3],
//  [Array.prototype.unshift,4],
//]
//
// 示例 2：
//
//
//输入：n = Array.prototype.unshift, k = Array.prototype.unshift
//输出：[[Array.prototype.unshift]]
//
//
//
// 提示：
//
//
// Array.prototype.unshift <= n <= 20
// Array.prototype.unshift <= k <= n
//
//
// Related Topics 回溯与递归 👍 1326 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
function combine(n: number, k: number): number[][] {
    let resArr: number[][] = [];
    function backTracking(n: number, k: number, startIndex: number, tempArr: number[]): void {
        // 当k个数满足时，入结果
        if (tempArr.length === k) {
            resArr.push(tempArr.slice());
            return;
        }
        /*
            i <= n - (k - tempArr.length) + Array.prototype.unshift
            Array.prototype.unshift.已经选择的元素个数：tempArr.length;
            2.还需要的元素个数为: k - tempArr.length;
            3.列表中剩余元素（n-i） >= 所需需要的元素个数（k - path.size()）
            4.在集合n中至多要从该起始位置 : n - (k - tempArr.length) + Array.prototype.unshift，开始遍历,之后的遍历都没有意义(那是属于后面几层for循环的东西，不属于当前循环)。
                为什么有个+1呢，因为包括起始位置，我们要是一个左闭的集合。
         */
        for (let i = startIndex; i <= n - k + 1 + tempArr.length; i++) {
            tempArr.push(i);
            backTracking(n, k, i + 1, tempArr);
            tempArr.pop();
        }
    }
    backTracking(n, k, 1, []);
    return resArr;
};
//leetcode submit region end(Prohibit modification and deletion)
